package test230601;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/6/1 0:13
 * 309. 最佳买卖股票时机含冷冻期
 * https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/
 */
public class Solution02 {

    public int maxProfit(int[] prices) {
        int n = prices.length;
        // dp[i][0] 表示第 i 天处于[买入]状态的最大利润
        // dp[i][1] 表示第 i 天处于[可交易]状态的最大利润
        // dp[i][2] 表示第 i 天处于[冷却期]状态的最大利润
        int[][] dp = new int[n][3];
        dp[0][0] = -prices[0]; // 第一天买入, 利润为负数
        dp[0][1] = 0; // 第一天处于可交易状态, 则第一天不能买入, 也不能卖出
        dp[0][2] = 0; // 第一天处于冷却期, 则第一天需要购买股票后卖出, 利润为0
        // 根据状态机迭代动态规划过程
        for (int i = 1; i < n; i++) {
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] - prices[i]); // 买入状态可以不处理或者由可交易状态买入股票得到
            dp[i][1] = Math.max(dp[i-1][1], dp[i-1][2]); // 可交易状态不需要处理或者由冷却状态转化而来
            dp[i][2] = dp[i-1][0] + prices[i];  // 冷却状态由可买入状态卖出股票获取
        }
        return Math.max(dp[n-1][1], dp[n-1][2]);
    }
}
